package com.fan.dijkstra;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 迪杰斯特拉算法，图中某一点到图中其它点的最短路径
 *
 * @author 19252
 * @date 2020/8/9
 */
public class DijkstraDemo {

    public static void main(String[] args) {
        DijkstraGraph graph = new DijkstraGraph(7);
        char[] vertexArray = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        graph.setVertexArray(vertexArray);
        // 为图添加边
        /*graph.setEdge(0, 1, 5);
        graph.setEdge(0, 2, 7);
        graph.setEdge(0, 6, 2);
        graph.setEdge(1, 0, 5);
        graph.setEdge(1, 3, 9);
        graph.setEdge(1, 6, 3);
        graph.setEdge(2, 0, 7);
        graph.setEdge(2, 4, 8);
        graph.setEdge(3, 1, 9);
        graph.setEdge(3, 5, 4);
        graph.setEdge(4, 2, 8);
        graph.setEdge(4, 5, 5);
        graph.setEdge(4, 6, 4);
        graph.setEdge(5, 3, 4);
        graph.setEdge(5, 4, 5);
        graph.setEdge(5, 6, 6);
        graph.setEdge(6, 0, 2);
        graph.setEdge(6, 1, 3);
        graph.setEdge(6, 4, 4);
        graph.setEdge(6, 5, 6);*/

        // A
        graph.setEdge(0, 1, 12);
        graph.setEdge(0, 5, 16);
        graph.setEdge(0, 6, 14);
        // B
        graph.setEdge(1, 0, 12);
        graph.setEdge(1, 2, 10);
        graph.setEdge(1, 5, 7);
        // C
        graph.setEdge(2, 1, 10);
        graph.setEdge(2, 3, 3);
        graph.setEdge(2, 4, 5);
        graph.setEdge(2, 5, 6);
        // D
        graph.setEdge(3, 2, 3);
        graph.setEdge(3, 4, 4);
        // E
        graph.setEdge(4, 2, 5);
        graph.setEdge(4, 3, 4);
        graph.setEdge(4, 5, 2);
        graph.setEdge(4, 6, 8);
        // F
        graph.setEdge(5, 0, 16);
        graph.setEdge(5, 1, 7);
        graph.setEdge(5, 2, 6);
        graph.setEdge(5, 4, 2);
        graph.setEdge(5, 6, 9);
        // G
        graph.setEdge(6, 0, 14);
        graph.setEdge(6, 4, 8);
        graph.setEdge(6, 5, 9);
        graph.showGraph();

        DijkstraResult.getShortestPath(graph, 6);
        for (ArrayList<Character> path : DijkstraResult.path) {
            System.out.println(path);
        }
        System.out.println(Arrays.toString(DijkstraResult.shortestPath));
    }
}

/**
 * 迪杰斯特拉算法生成的结果
 * ggyugyu
 */
class DijkstraResult {

    /**
     * 记录起始顶点到图上其它顶点的最短距离
     */
    public static int[] shortestPath;

    /**
     * 保存其实顶点到其他顶点的遍历路径
     */
    public static ArrayList<ArrayList<Character>> path = new ArrayList<>();

    /**
     * 获取遍历的最短路径
     *
     * @param graph 图
     */
    public static void getShortestPath(DijkstraGraph graph) {
        getShortestPath(graph, 0);
    }

    /**
     * 指定获取当前顶点到其它顶点的最短路径
     *
     * @param graph  图
     * @param vertex 起始顶点
     */
    public static void getShortestPath(DijkstraGraph graph, int vertex) {
        // shortestPath 保存最原始的当前顶点到其他顶点的原始距离
        shortestPath = new int[graph.getVertexNum()];
        // 初始化
        Arrays.fill(shortestPath, graph.getUnreachable());
        // 初始化路径的保存对象
        for (int i = 0; i < graph.getVertexNum(); i++) {
            ArrayList<Character> temp = new ArrayList<>();
            // 遍历起点
            temp.add(graph.getVertexArray()[vertex]);
            path.add(temp);
        }
        // 开始获取最短路径
        addTraversePath(shortestPath, graph, vertex);
        graph.getIsVisited()[vertex] = true;
        for (int i = 0; i < graph.getVertexNum(); i++) {
            for (int j = 0; j < graph.getVertexNum(); j++) {
                if(!graph.getIsVisited()[j]) {
                    updateTraversePath(shortestPath, graph, j);
                }
            }
        }
    }

    /**
     * 初始化第一个顶点
     * @param shortestPath 第一个顶点的可遍历路径
     * @param graph 图对象
     * @param vertex 顶点编号
     */
    public static void addTraversePath(int[] shortestPath, DijkstraGraph graph, int vertex) {
        for (int i = 0; i < shortestPath.length; i++) {
            // 根据当前顶点的与各个顶点的权值更新到各个顶点的最短路径
            if (graph.getMatrix()[vertex][i] < shortestPath[i]) {
                shortestPath[i] = graph.getMatrix()[vertex][i];
                path.get(i).add(graph.getVertexArray()[i]);
            }
        }
    }

    public static void updateTraversePath(int[] shortestPath, DijkstraGraph graph, int vertex) {
        graph.getIsVisited()[vertex] = true;
        for (int i = 0; i < shortestPath.length; i++) {
            // 判断以当前顶点为遍历起点的距离
            // A->C->B < A->B 就将 A->的距离置为 A->C->B的距离 （前提A->C是可行的）
            if (graph.getMatrix()[vertex][i] + shortestPath[vertex] < shortestPath[i]) {
                // 最短路径更新
                shortestPath[i] = graph.getMatrix()[vertex][i] + shortestPath[vertex];
                // 用来保存新的路径
                ArrayList<Character> tempCharacters = new ArrayList<>();
                // 将原来的到达当前顶点的路径复制 就是将例子 A->C 复制过来
                tempCharacters.addAll(0, path.get(vertex));
                // 将 A->B 替换成 A->C
                path.set(i, tempCharacters);
                // 再将 B 放入 A->C中，就可以得到新的 A到B的最短路径 A->C->B
                path.get(i).add(graph.getVertexArray()[i]);
            }
        }
    }
}

class DijkstraGraph {
    /**
     * 图中顶点的个数
     */
    private int vertexNum;

    /**
     * 图中的顶点
     */
    private char[] vertexArray;

    /**
     * 邻接矩阵
     */
    private int[][] matrix;

    /**
     * 标记图中对应下标的顶点是否被访问过
     */
    private boolean[] isVisited;

    /**
     * unreachable 不可达
     * unreachable 定义为一个非常大的值
     * 表示两点之间不连通
     */
    private int unreachable = 1000000000;

    public DijkstraGraph(int vertexNum) {
        this.vertexNum = vertexNum;
        matrix = new int[vertexNum][vertexNum];
        isVisited = new boolean[vertexNum];
        // 除了顶点本身默认图中所有的点不可达
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                if (i == j) {
                    matrix[i][j] = 0;
                } else {
                    matrix[i][j] = unreachable;
                }
            }
        }
    }

    /**
     * 为图填充数据，设置图中两点的距离
     *
     * @param vertex1 顶点
     * @param vertex2 顶点
     * @param weight  两个连接的顶点间的权值（在这里就是两点间的距离）
     */
    public void setEdge(int vertex1, int vertex2, int weight) {
        matrix[vertex1][vertex2] = weight;
    }

    public void showGraph() {
        for (int[] vertexLink : matrix) {
            for (int weight : vertexLink) {
                System.out.printf("%-15d", weight);
            }
            System.out.println();
        }
    }

    public int getVertexNum() {
        return vertexNum;
    }

    public void setVertexNum(int vertexNum) {
        this.vertexNum = vertexNum;
    }

    public char[] getVertexArray() {
        return vertexArray;
    }

    public void setVertexArray(char[] vertexArray) {
        this.vertexArray = vertexArray;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    public void setMatrix(int[][] matrix) {
        this.matrix = matrix;
    }

    public boolean[] getIsVisited() {
        return isVisited;
    }

    public void setIsVisited(boolean[] isVisited) {
        this.isVisited = isVisited;
    }

    public int getUnreachable() {
        return unreachable;
    }
}
